package com.tzl.leetcode.editor.cn;


import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 * 答案一：广度优先搜索
 * <pre>
 *      public boolean isSameTree(TreeNode p, TreeNode q) {
 *         Queue<TreeNode> queueP = new LinkedList<>();
 *         Queue<TreeNode> queueQ = new LinkedList<>();
 *         queueP.add(p);
 *         queueQ.add(q);
 *         while (!queueP.isEmpty()) {
 *             TreeNode pVal = queueP.poll();
 *             TreeNode qVal = queueQ.poll();
 *             if (pVal == null && qVal == null) {
 *                 continue;
 *             }
 *             if (pVal == null || qVal == null) {
 *                 return false;
 *             }
 *             if (pVal.val == qVal.val) {
 *                 queueP.add(pVal.left);
 *                 queueP.add(pVal.right);
 *                 queueQ.add(qVal.left);
 *                 queueQ.add(qVal.right);
 *             } else {
 *                 return false;
 *             }
 *         }
 *         return true;
 *     }
 * </pre>
 * 答案二：深度优先搜索
 * <pre>
 *     public boolean isSameTree(TreeNode p, TreeNode q) {
 *         if (p == null && q == null) {
 *             return true;
 *         } else if (p == null || q == null) {
 *             return false;
 *         } else if (p.val != q.val) {
 *             return false;
 *         } else {
 *             return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
 *         }
 *     }
 * </pre>
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queueP = new LinkedList<>();
        Queue<TreeNode> queueQ = new LinkedList<>();
        queueP.add(p);
        queueQ.add(q);
        while (!queueP.isEmpty()) {
            TreeNode pVal = queueP.poll();
            TreeNode qVal = queueQ.poll();
            if (pVal == null && qVal == null) {
                continue;
            }
            if (pVal == null || qVal == null) {
                return false;
            }
            if (pVal.val == qVal.val) {
                queueP.add(pVal.left);
                queueP.add(pVal.right);
                queueQ.add(qVal.left);
                queueQ.add(qVal.right);
            } else {
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
